'''
现有n个数,设计算法得到前k大的数.(k<n)
解决思路:
    排序后切片 O(nlogn)
    排序lowB三人组:冒泡,插入,选择 O(kn)
    堆排序:O(nlogk)
堆排序解决思路:
    取列表前k个元素建立一个小根堆,

'''
def sift(li,low,high):
# li:列表 ,low:堆的堆顶元素 ,high:堆的最后一个元素
    i = low  # i指向根节点
    j = 2*i + 1  # j是i的左孩子
    tmp = li[low]   # 把堆顶存起来
    while j<= high:   # 只要j位置有数据
        if j + 1 <= high and li[j+1] < li[j]:  #如果右孩子首先要有并且比较大
            j = j + 1   # 把j 指向右孩子
        if li[j] < tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:   #tmp更大,把tmp放到i的位置上
            li[i] = tmp
            break
    else:
        li[i] = tmp  # 把tmp最后的叶子结点上

def topk(li,k):
    heap = li[0:k]
    for i in range((k-2)//2,-1,-1):
        sift(heap,i,k-1)
        #1,建堆
    for i in range(k,len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap,0,k-1)
        #2,遍历
    for i in range(k-1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        sift(heap,0,i-1)
        #3.出数
    return heap

import random
li = list(range(1000))
random.shuffle(li)
print(topk(li,10))